package Tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 题目 ：二叉树的右序遍历
 * 题目详述 ：
 * 给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
 *
 * 后序遍历 ；
 * [左子节点 ， 右子节点 ， 根节点]
 */
public class PostorderTraversal {
    /**
     * 方法一 ：递归
     * 注意 ：递归适用于二叉树的前/中/后序遍历
     *
     * （1）初始化结果集合list；
     * （2）调用dfs(当前遍历节点node , 结果集合list)（方法结束条件 ；当前遍历节点node == null）
     */
    /*
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>(); // 用来存储结果集合
        // dfs方法所传递的参数，即（当前正在遍历的树节点 ， list结果集合）
        dfs(root , list);
        return list;
    }
    public void dfs(TreeNode node , List<Integer> list){
        if(node == null){
            return;
        }
        // 遍历左子树，直至左节点不存在为止；
        dfs(node.left , list);
        dfs(node.right , list);
        // 将当前遍历节点加入到结果集合（由于（1）其没有左子节点/（2）其左子节点已经加入到结果集合中）
        list.add(node.val);
    }
     */
    /**
     * 方法二 ：迭\     * 后序遍历 ：[左子节点 ， 右子节点 。 父节点]
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        // 后序遍历的栈中元素，出栈条件在于父节点的右子树已经被遍历过
        // 核心 ：父节点的右子树已经被遍历过  《===》 当前节点是父节点 && 父节点前一个被遍历的节点是父节点的右子节点
        // 解决方法 ：使用preNode节点，来保存上一个被遍历的节点
        TreeNode node = root;
        // 初始化上一个遍历节点为null
        TreeNode preNode = null;
        while( node != null || !stack.isEmpty()){
            // 与之前（先序/中序遍历）的结束条件一样，
            // 当前遍历的节点为空 || stack中所有的元素也被遍历到（stack栈中所存储的元素是所有父节点）
            while(node != null){
                // 向左遍历，没问题，由于无论前中后序遍历，都是先遍历左子树（左子节点）
                stack.push(node);
                node = node.left;
            }
            // 此处必须将空节点，变成其父节点
            node = stack.peek();
            // 后续的if-else判断，出现条件：当node节点为空时，所以需要去重新获取遍历节点的父节点
            // 存储所以父节点的栈顶元素，即为当前节点的父节点；
            if(node.right != null && node.right != preNode){
                node = node.right;
            }
            else{
                // 若是满足（1）父节点的右子节点为null（2）父节点的右子节点为上一个遍历的节点,
                // 即，说明父节点的右子树已经被遍历了，所以直接将父节点加入到结果集合 && 弹出栈顶元素（当前遍历的元素）
                result.add(node.val);
                stack.pop();
                preNode = node;
                // 此处的node必须为null，
                // 若是将其置为栈顶元素（父节点）的话，会出现再次执行while（左子节点遍历）；
                // 由于此节点为其父节点的左子节点，代表了其左子树已经被遍历过；
                // 由于是后序遍历，所以需要判断其右子树是否已经被遍历过；
                // 若是未遍历过的话，只需要将当前遍历的节点指向其右子节点，同时将此父节点加入到栈中
                node = null;
            }
        }
        return result;
    }
}
